BOJ

[Silver IV] 수강변경 - 23305

문제 링크

성능 요약

메모리: 188188 KB, 시간: 736 ms

분류

구현, 그리디 알고리즘

제출 일자

2025년 10월 6일 11:02:52

문제 설명

20XX년, 전국 유일의 마일리지 수강신청 제도를 채택하고 있는 연세대는 수강변경에서도 혁신적인 시스템을 도입하려고 한다.

20XX년을 기점으로 수강변경 기간 동안에는 "수업 교환"이 허용된다!

수업 교환은 두 사람이 서로 다른 수업을 교환하는 것으로, 두 사람 모두의 동의가 있어야만 수업 교환이 가능하다.

이때, 삼자 교환은 불가능하지만, 두 사람이 수업을 교환하고, 교환한 사람 중 다른 사람이 그 수업을 또 다른 사람과 교환하는 것은 허용된다.

처음 제도가 도입되었을 때는 말이 많았지만, 서로의 전공 수업을 수강하고 싶은 학생들이 수업을 교환하거나, 마일리지가 많이 남는 졸예자들이 후배들에게 수업을 물려주는 등의 좋은 상황이 많이 생기고 있다.

어느 때와 같이 수강변경이 시작되었다. 학생들이 수강하고 싶은 수업이 $1$개씩 주어지고, 교환하고 싶은 수업이 $1$개씩 주어질 때, 수업 교환이 끝나고 본인이 원하는 수업을 수강하지 못하는 인원의 최솟값을 구해보자.

입력

첫 줄에 학생의 수 $N$이 주어진다. ($1\le N\le 1000000$)

두 번째 줄에 정수 $A_1,A_2,\cdots ,A_N$이 주어진다. 여기서 $A_i$는 $i$번 학생이 현재 신청한 수업이며, 동시에 교환하고 싶은 수업의 번호를 의미한다. ($1\le A_i\le 1000000$)

세 번째 줄에 정수 $B_1,B_2,\cdots ,B_N$이 주어진다. 여기서 $B_i$는 $i$번 학생이 교환을 통해 수강하고 싶은 수업의 번호를 의미한다. ($1\le B_i\le 1000000$)

모든 입력은 공백으로 구분되어 주어진다.

출력

모든 학생들이 최적의 방법을 사용해서 수업 교환을 완료했을 때, 원하는 수업을 수강하지 못하는 학생들의 수를 출력한다.

소스 코드

• 수강변경.java